package day_2022_7_to_8.day48;

import java.util.ArrayList;
import java.util.List;

/**
 * @author haomin
 * @date 2022/08/24 12:12
 **/
public class Day39_2_Num93_RestoreIpAddresses {
    class Solution {
        List<String> ans = new ArrayList<>();
        public List<String> restoreIpAddresses(String s) {
            List<String> ret = new ArrayList<>();
            dfs(s, ret, 0);
            return ans;
        }
        private void dfs(String s, List<String> ret, int start) {
            if(ret.size() > 4) return;
            if(start == s.length() && ret.size() == 4){
                ans.add(toString(ret));
                return;
            }
            for(int i = start; i < s.length(); ++i){
                String str = s.substring(start, i+1);
                if(!isLegal(str)) continue;
                ret.add(str);
                dfs(s, ret, i+1);
                ret.remove(ret.size()-1);
            }
        }

        private boolean isLegal(String str) {
            if(str.length() == 1) return true;
            if(str.length() > 3) return false;
            if(str.charAt(0) == '0') return false;
            if(Integer.valueOf(str) > 255) return false;
            return true;
        }

        private String toString(List<String> ret) {
            StringBuffer sb = new StringBuffer();
            for(int i = 0; i < ret.size(); ++i){
                sb.append(ret.get(i));
                if(i != ret.size()-1){
                    sb.append(".");
                }
            }
            return sb.toString();
        }
    }
}